from typing import List


class Solution:
    """
     方法： 使用动态规划求解带障碍物的唯一路径问题
            使用一维数组f[j]表示到达当前行第j列的路径数
            遇到障碍物时该位置的路径数置为0
            否则路径数等于其上方和左方路径数之和
     
     Args:
         obstacleGrid: List[List[int]] - 表示网格的二维数组，1表示障碍物，0表示空位
     
     Returns:
         int: 从左上角到右下角的唯一路径数
     
     Time: O(m*n) - m和n分别为网格的行数和列数，需要遍历整个网格
     
     Space: O(n) - 使用一维数组存储中间结果，n为网格的列数
     """
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
       n = len(obstacleGrid[0])
       f = [0] *  (n + 1)
       f[1] = 1
       for row in obstacleGrid:
          for j,x in enumerate(row):
            if x == 0:
                f[j + 1] += f[j]
            else:
                f[j + 1] = 0
       return f[n]